package leetcode;

import java.util.*;
import java.util.stream.Collectors;

public class Lc22 {

    HashSet<String> set = new HashSet<>();
    public List<String> generateParenthesis(int n) {

        getAns(n, "");

        return new ArrayList<>(set);
    }
    public void getAns(int n, String str) {
        if (n == 0) {
            set.add(str);
            return;
        }
        if (str.length() == 0) {
            getAns(n - 1, "()");
        } else {
            HashSet<String> st = new HashSet<>();
            for (int i = 0; i < str.length(); i++) {
                String temp = str.substring(0, i) + "()" + str.substring(i, str.length());
                st.add(temp);
            }
            st.add(str + "()");
            for (String s : st) {
                getAns(n - 1, s);
            }
        }

    }

    public static void main(String[] args) {
        Lc22 lc22 = new Lc22();
        lc22.generateParenthesis(3).forEach(System.out::println);



//        String[] s1 = {"(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"};
//        String[] s2 = {"()()()()","(()(()))","(()())()","()()(())","(((())))","(())()()","()((()))","()(())()","()(()())","(()()())","((()()))","((()))()","((())())" };
////        Arrays.sort(s1);
////        Arrays.sort(s2);
////        Arrays.stream(s1).sorted().forEach(System.out::print);
////        System.out.println();
////        Arrays.stream(s2).sorted().forEach(System.out::print);
//
//        String t = Arrays.stream(s1).sorted().collect(Collectors.joining(","));
//        System.out.println(t);
//        t = Arrays.stream(s2).sorted().collect(Collectors.joining(","));
//        System.out.println(t);
//
//
//        LinkedList<String> list = new LinkedList<>();
//        list.add("qq");
//        list.add("ee");
//        System.out.println(list.stream().collect(Collectors.joining()));
    }


}
